package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/22 14:12
 */
public class M0811 {

    int[] coins = {1, 5, 10, 25};

    // 暴力尝试
    public int waysToChange(int n) {
        return (int) (process(0, n) % 1000000007);
    }

    // i 代表当前来到哪儿张硬币, rest代表还剩下多少钱要组成
    public long process(int i, int rest) {
        if (i == coins.length) return rest == 0 ? 1 : 0;
        int ways = 0;
        for (int nums = 0; nums * coins[i] <= rest; nums++) {
            ways += process(i + 1, rest - nums * coins[i]);
        }
        return ways;
    }

    public int dp(int n) {
        int R = coins.length + 1, C = n + 1;
        long[][] dp = new long[R][C];
        dp[R - 1][0] = 1;

        for (int r = R - 2; r >= 0; r--) {
            for (int c = 0; c < C; c++) {
                int ways = 0;
                for (int nums = 0; nums * coins[r] <= c; nums++) {
                    ways += dp[r + 1][c - nums * coins[r]];
                }
                dp[r][c] = ways;
            }
        }
        return (int) (dp[0][n] % 1000000007);
    }
    public int dp2(int n) {
        int R = coins.length + 1, C = n + 1;
        long[][] dp = new long[R][C];
        dp[R - 1][0] = 1;

        for (int r = R - 2; r >= 0; r--) {
            for (int c = 0; c < C; c++) {
                dp[r][c] = dp[r+1][c] + (c-coins[r] >= 0? dp[r][c-coins[r] ] : 0);
            }
        }
        return (int) (dp[0][n] % 1000000007);
    }


    // for test
    public static void main(String[] args) {
        M0811 test = new M0811();

        int n = 20;
        System.out.println(test.waysToChange(n));
        System.out.println(test.dp(n));
        System.out.println(test.dp2(n));
    }

}
